A hypergraph is a generalization of a graph in which an edge can connect any number of vertices. Formally, a hypergraph G=(V, E) is defined as a set of vertices (or nodes) V and a set of hyperedges (or edges) E, where each hyperedge is a subset of the vertex set V, and the size or order of a hyperedge is the cardinality of this subset.
Hypergraph partitioning is an important problem with extensive application to many areas, including very large scale integration (VLSI) integrated circuit design, efficient storage of large databases on disks, and data mining. The k-way partitioning problem assigns each node of a hypergraph into one of k bins while attempting to minimize the “cut metric”, i.e., the number of hyperedges that connect nodes assigned to multiple bins. Real world partitioning problems often have multi-valued cost functions in addition to the edge-cost, and obey various constraints.
For an application that partitions integrated circuit designs, the hypergraph can be thought of as a netlist that represents a design to be partitioned into k FPGA units of a system for FPGA-based prototyping. In addition to the cut metric, the application requires attention to the timing of the system and to the number and configuration of the wires available to interconnect the FPGA units.
A common method used for partitioning is the multi-level partitioning approach developed by Karypis and Kumar for the hMETIS system. This approach begins by coarsening the hypergraph using connectivity-based clustering and then repeatedly applying a local search optimization heuristic (local search) to partition the hypergraph followed by “un-coarsening” the graph. A common local search optimization heuristic is the Fiduccia-Mattheyses algorithm.
The quality of results (QoR) of the multi-level partitioning approach is sensitive to the quality of the initial solution at the coarsest level of the hypergraph. Local search can get stuck at local minima. A common approach used to work around this limitation is to run multiple trials of local search, each with a different seed solution, and to keep the best resulting solution.
A meta-heuristic implements a strategy to guide the search process for a complex optimization problem with the goal of efficiently exploring the solution space to find near-optimal solutions. A partitioning meta-heuristic is the method of generating seed solutions for local search. Common meta-heuristic approaches include random solution generation and genetic optimization.